package drds.server.execute_engine.data_handling.tmp;

import java.util.ArrayList;
import java.util.List;

import drds.server.net.packet.RowDataPacket;

/**
 * 最大堆排序，适用于顺序排序
 * 
 * 
 */
public class MaxHeap implements Heap {

	private RowDataComparator rowDataComparator;
	private List<RowDataPacket> rowDataPacketList;

	public MaxHeap(RowDataComparator rowDataComparator, int size) {
		this.rowDataComparator = rowDataComparator;
		this.rowDataPacketList = new ArrayList<>();
	}

	@Override
	public void buildHeap() {
		int size = rowDataPacketList.size();
		for (int i = size / 2 - 1; i >= 0; i--) {
			heapifyRecursive(i, size);
		}
	}

	private void heapify(int i, int size) {
		int max = 0;
		int mid = size >> 1;// ==size/2
		while (i <= mid) {
			max = i;
			int left = i << 1;
			int right = left + 1;
			if (left < size && rowDataComparator.compare(rowDataPacketList.get(left), rowDataPacketList.get(i)) > 0) {
				max = left;
			}
			if (right < size && rowDataComparator.compare(rowDataPacketList.get(right), rowDataPacketList.get(max)) > 0) {
				max = right;
			}
			if (i == max) {
				break;
			}
			if (i != max) {
				RowDataPacket tmp = rowDataPacketList.get(i);
				rowDataPacketList.set(i, rowDataPacketList.get(max));
				rowDataPacketList.set(max, tmp);
				i = max;
			}
		}

	}

	// 递归版本
	protected void heapifyRecursive(int i, int size) {
		int l = left(i);
		int r = right(i);
		int max = i;
		if (l < size && rowDataComparator.compare(rowDataPacketList.get(l), rowDataPacketList.get(i)) > 0) {
			max = l;
		}
		if (r < size && rowDataComparator.compare(rowDataPacketList.get(r), rowDataPacketList.get(max)) > 0) {
			max = r;
		}
		if (i == max) {
			return;
		}
		swap(i, max);
		heapifyRecursive(max, size);
	}

	private int right(int i) {
		return (i + 1) << 1;
	}

	private int left(int i) {
		return ((i + 1) << 1) - 1;
	}

	private void swap(int i, int j) {
		RowDataPacket tmp = rowDataPacketList.get(i);
		RowDataPacket elementAt = rowDataPacketList.get(j);
		rowDataPacketList.set(i, elementAt);
		rowDataPacketList.set(j, tmp);
	}

	@Override
	public RowDataPacket getRootRowDataPacket() {
		return rowDataPacketList.get(0);
	}

	@Override
	public void setRoot(RowDataPacket root) {
		rowDataPacketList.set(0, root);
		heapifyRecursive(0, rowDataPacketList.size());
	}

	@Override
	public List<RowDataPacket> getRowDataPacketList() {
		return rowDataPacketList;
	}

	@Override
	public void add(RowDataPacket row) {
		rowDataPacketList.add(row);
	}

	@Override
	public boolean addIfRequired(RowDataPacket row) {
		// 淘汰堆里最小的数据
		RowDataPacket root = getRootRowDataPacket();
		if (rowDataComparator.compare(row, root) < 0) {
			setRoot(row);
			return true;
		}
		return false;
	}

	@Override
	public void heapSort(int size) {
		final int total = rowDataPacketList.size();
		// 容错处理
		if (size <= 0 || size > total) {
			size = total;
		}
		final int min = size == total ? 0 : (total - size - 1);

		// 末尾与头交换，交换后调整最大堆
		for (int i = total - 1; i > min; i--) {
			swap(0, i);
			heapifyRecursive(0, i);
		}
	}

}
